package 剑指offer;

public class 剑指Offer10II青蛙跳台阶问题 {
    public int numWays(int n) {
        //递归
        // if(n <= 1) return 1;
        // if (n == 2) return 2;
        //存在多个
        // return numWays(n-1) + numWays(n-2);

        //basecase：
        // int[] dp = new int[n+1];

        //动规
        if(n < 2){
            return 1;
        }
        int a = 1;
        int b = 1;
        int c = 0;
        for(int i = 2; i <= n;i++){
            c = (a + b) % (int) (1e9+7);
            a = b;
            b = c;
        }
        return c;
    }
}
